package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 951. 翻转等价二叉树
 * @author feizns
 * @since 2020/3/14
 */
public class FlipEquiv {

    public static void main(String[] args) {

    }

    public static boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if ( root1 == root2 )
            return true;
        else if ( root1 == null || root2 == null )
            return false;

        if ( root1.val == root2.val ) {
            if ( root1.left == null ) {
                if ( root2.left == null )
                    return flipEquiv(root1.right, root2.right);
                if ( root2.right == null )
                    return flipEquiv(root1.right, root2.left);
            } else if ( root1.right == null ) {
                if ( root2.left == null )
                    return flipEquiv(root1.left, root2.right);
                if ( root2.right == null )
                    return flipEquiv(root1.left, root2.left);
            } else {
                boolean left = (flipEquiv(root1.left, root2.left) || flipEquiv(root1.left, root2.right));
                boolean right = (flipEquiv(root1.right, root2.left) || flipEquiv(root1.right, root2.right));
                return left && right;
            }
        }
        return false;
    }

}
